// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

#include <sstream>
#include <queue>
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    /**
    * 先序序列：[pre_left, pre_right]
    * 中序序列：[in_left, in_right]
    * 要点：找到根节点在中序序列中的位置。递归的传入先序序列的左、右边界，中序序列的左右边界
    */
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_right){
        if(pre_left > pre_right || in_left > in_right) return nullptr;
        int root_val = preorder[pre_left];
        TreeNode* root = new TreeNode(root_val);
        auto pos = find(inorder.begin(), inorder.end(), root_val);
        int pos_root_inorder = pos - inorder.begin();

        root->left = build(preorder, inorder, pre_left + 1, pos_root_inorder - in_left + pre_left, in_left, pos_root_inorder - 1);

        root->right = build(preorder, inorder, pos_root_inorder - in_left + pre_left + 1, pre_right, pos_root_inorder + 1, in_right);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* buildTree2(vector<int>& preorder, vector<int>& inorder){
        if(preorder.size() == 0 || inorder.size() == 0) return nullptr;

        TreeNode* root = new TreeNode(preorder.front());
        auto pos = std::find(inorder.begin(), inorder.end(), preorder[0]);

        for(int i = 0; i < preorder.size(); i++)
            if(preorder[0] == inorder[i]){
                vector<int> pre_left;
                int pre_left_length = pos - inorder.begin();
                auto pre_left_end = preorder.begin() + pre_left_length;
                pre_left.assign(preorder.begin()+1, pre_left_end+1);
                
                vector<int> pre_right;
                int pre_right_length = inorder.size() - (pre_left_length+1);
                pre_right.assign(pre_left_end + 1, preorder.end());

                vector<int> in_left;
                in_left.assign(inorder.begin(), pos );

                vector<int> in_right;
                in_right.assign(pos + 1, inorder.end());

                root->left = buildTree2(pre_left, in_left);
                root->right = buildTree2(pre_right, in_right);
            }

        return root;
        
        

    }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

string treeNodeToString(TreeNode* root) {
    if (root == nullptr) {
      return "[]";
    }

    string output = "";
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        if (node == nullptr) {
          output += "null, ";
          continue;
        }

        output += to_string(node->val) + ", ";
        q.push(node->left);
        q.push(node->right);
    }
    return "[" + output.substr(0, output.length() - 2) + "]";
}

int main() {
    vector<int> preorder = stringToIntegerVector("[1,2]");
    vector<int> inorder = stringToIntegerVector("[2,1]");
    
    TreeNode* ret = Solution().buildTree2(preorder, inorder);
    // TreeNode* ret = Solution().buildTree(preorder, inorder);

    string out = treeNodeToString(ret);
    cout << out << endl;
    return 0;
}